class Solution1 {
    int[] xx = {1, -1, 0, 0, -1, -1, 1, 1};
    int[] yy = {0, 0, 1, -1, -1, 1, -1, 1};
    int n, m;

    public char[][] updateBoard(char[][] board, int[] click) {
        n = board.length;
        m = board[0].length;
        int x = click[0], y = click[1];
        if (board[x][y] == 'M') {
            board[x][y] = 'X';
        } else if (board[x][y] == 'E') {
            dfs(board, x, y);
        }
        return board;
    }

    public void dfs(char[][] board, int x, int y) {
        System.out.println(x + " " + y);
        if(board[x][y] != 'E') return;

        int count = 0;
        for (int i = 0; i < 8; i++) {
            int dx = x + xx[i];
            int dy = y + yy[i];
            if (dx >= 0 && dx < n && dy >= 0 && dy < m && board[dx][dy] == 'M') {
                count++;
            }
        }

        if(count == 0) {
            board[x][y] = 'B';
            for (int i = 0; i < 8; i++) {
                int dx = x + xx[i];
                int dy = y + yy[i];
                if (dx >= 0 && dx < n && dy >= 0 && dy < m) {
                    dfs(board,dx,dy);
                }
            }
        }else {
            board[x][y] = (char)('0' + count);
        }
    }
}

class Solution {
    int count = 0;
    int m,n,cnt;
    boolean[][] vis;
    public int wardrobeFinishing(int _m, int _n, int _cnt) {
        m = _m;
        n = _n;
        cnt = _cnt;
        vis = new boolean[m][n];
        vis[0][0] = true;
        dfs(0,0);
        return count;
    }
    public void dfs(int x, int y) {
        count++;
        //向右
        if(y+1 < n && digit(x) + digit(y+1) <= cnt && !vis[x][y+1]) {
            vis[x][y+1] = true;
            dfs(x,y+1);
        }
        //向下
        if(x+1 < m && digit(x+1) + digit(y) <= cnt && !vis[x+1][y]) {
            vis[x+1][y] = true;
            dfs(x+1, y);
        }
    }
    public int digit(int x) {
        int sum = 0;
        while (x != 0) {
            sum += x%10;
            x /= 10;
        }
        return sum;
    }
}



















public class Test {

}
